#include <stdio.h>
#include <iostream>
#include <conio.h>
using namespace std;
void ShakerSort(int a[], int N)
{
   int i, k, left, right;
   k = 0;
   left = 0;
   right = N - 1;
   while (left < right) {
       for (i = right; i > left; i--)
           if (a[i] < a[i - 1]) {
               swap(a[i], a[i - 1]); 
               k = i; 
           }
       left = k;
       for (i = left; i < right; i++)
           if (a[i] > a[i + 1]) {
              swap(a[i], a[i + 1]);
              k = i;
          }
      right = k;
	  for(int i = 0; i < N ;i++)
		cout<<a[i]<<" ";
	  cout<<"\n";
   }
}
void main()
{
	int a[16]={16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
	int n=16;
	ShakerSort(a,n);
//	getch();
}